package cn.edu.ncepu;

public class CatalanNumber {

    /**
     * 计算卡特兰数（以1开始，C1=1, C2=1, C3=2, C4=5...）
     * @param n 卡特兰数的项数（n≥1）
     * @return 第n个卡特兰数
     */
    public static int catalan(int n) {
        // 边界条件：n<3时返回1（对应C1=1, C2=1）
        if (n < 3) {
            return 1;
        }

        // 数组存储卡特兰数，array[0]对应C1，array[1]对应C2，array[i]对应C(i+1)
        int[] array = new int[n];
        // 初始化：C1=1（array[0]），C2=1（array[1]）
        array[0] = 1;
        array[1] = 1;

        // 计算C3到Cn（对应数组索引2到n-1）
        for (int i = 2; i < n; i++) {
            // 计算第i+1个卡特兰数：C(i+1) = Σ(C(j+1) * C(i-j)) （j从0到i-1）
            // 等价于 array[i] = Σ(array[j] * array[i-j-1])
            for (int j = 0; j < i; j++) {
                array[i] += array[j] * array[i - j - 1];
            }
        }

        // 返回第n个卡特兰数（对应数组最后一个元素）
        return array[n - 1];
    }

    // 测试验证
    public static void main(String[] args) {
        System.out.println(catalan(1));  // 输出1
        System.out.println(catalan(2));  // 输出1
        System.out.println(catalan(3));  // 输出2
        System.out.println(catalan(4));  // 输出5
        System.out.println(catalan(5));  // 输出14
        System.out.println(catalan(6));  // 输出42
    }
}